{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Clustering"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dans les deux dernires cours, on a rencontré deux situations d'apprentissage différentes.\n",
    "\n",
    "Dans le premier scénario, on cherchait à apprendre à classer des objets : à partir d'un ensemble d'exemples, on cherchait à apprendre à classer de nouveaux objets.\n",
    "Par exemple, à partir d'une base de données comportant les caractéristiques de certains fruits, on cherchait à apprendre à reconnaître des fruits.\n",
    "On parlait alors **d'apprentissage supervisé**, car on explique à la machine ce qu'elle doit trouver, et elle apprend à le reconnaître.\n",
    "\n",
    "Dans le second scénario, on cherchait à donner de la structure à un ensemble : à partir d'un ensemble de sites internet, et des liens qui existent entre eux, on cherchait à déterminer un classement des sites par ordre d'importance sur internet.\n",
    "On parlait alors **d'apprentissage non supervisé**, car on ne donnait à la machine aucun exemple permettant de déterminer ce classement, elle l'établissait d'elle-même.\n",
    "\n",
    "C'est cette capacité à donner de la structure à un ensemble de données qui caractérise l'apprentissage non-supervisé.\n",
    "Dans ce TP, on ne cherchera plus à établir un classement entre des objets, mais à les regrouper en groupes d'objets similaires.\n",
    "\n",
    "Ce problème est un problème difficile, car on ne connaît absolument rien de ces groupes : on ne sait pas *a priori* combien il y en a, ni quelles sont leurs caractéristiques.\n",
    "\n",
    "On doit alors nécessairement faire une hypothèse sur nos données.\n",
    "Par exemple, on peut supposer que nos données sont réparties en groupes homogènes, c'est-à-dire en groupes dans lesquels les points sont proches les uns des autres, tout en étant éloignés des points des autres groupes.\n",
    "Cela demande naturellement de définir une notion de distance appropriée, et on va étudier cela dans ce TP.\n",
    "\n",
    "**Ce TP est à rendre pour le vendredi 9 avril avant le cours à 14h15. Vous pouvez le rendre en binômes si vous voulez, à condition de bien me le signaler.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from sklearn import datasets "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Des Jeux de Données\n",
    "\n",
    "La fonction `make_blobs` de `sklearn` permet de générer des données naturellement regroupées en plusieurs groupes.\n",
    "Par exemple, on peut générer un dataset comportant deux groupes :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "X_2blobs, y_2blobs = datasets.make_blobs(200, 2, centers=2, cluster_std=0.5, random_state=42)\n",
    "\n",
    "plt.scatter(X_2blobs[:,0], X_2blobs[:, 1], c=y_2blobs, cmap='Dark2')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question 1.** Générez un dataset `(X_5blobs, y_5blobs)` avec la fonction `datasets.make_blobs` qui comporte $500$ points, en deux dimensions, répartis en $5$ groupes, et affichez le.\n",
    "\n",
    "*Vous pourrez vous aider de la documentation de la fonction `make_blobs` en exécutant le code `help(datasets.make_blobs)`.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#~~~ générez un dataset avec 5 blobs ~~~"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pour la suite, on va utiliser les deux jeux de données suivants :\n",
    "* un avec 3 groupes, mais pas complètement séparés : `(X_blobs, y_blobs)` ;\n",
    "* un avec 2 groupes, séparés mais s'entre-mêlant : `(X_moons, y_moons)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "centres = [[2, 1], [-1, -2], [1, -1]]\n",
    "X_blobs, y_blobs = datasets.make_blobs(n_samples=300, centers=centres, cluster_std=.5, random_state=42)\n",
    "\n",
    "X_moons, y_moons = datasets.make_moons(n_samples=500, noise=0.05, random_state=42)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question 2.** Affichez les deux datasets."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fig, ax = plt.subplots(1, 2, figsize=(10, 5))\n",
    "\n",
    "#~~~ affichez les deux datasets X_blobs et X_moons avec les bonnes couleurs ~~~"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## KMeans\n",
    "\n",
    "On va maintenant chercher à retrouver à retrouver ces groupes à partir de la seule connaissance des points (et aucune connaissance des groupes auquel chacun des points appartient !).\n",
    "C'est un problème d'apprentissage non supervisé : le **clustering**.\n",
    "\n",
    "Pour cela, une méthode simple, mais qui a largement fait ses preuves, est l'algorithme KMeans.\n",
    "Cette méthode représente les groupes (\"clusters\") par un point : le centre de ce groupe.\n",
    "Ainsi, on peut voir cela de deux façons :\n",
    "1. Un ensemble $S = \\{s_1, \\dots, s_K\\}$ de points de notre espace définissent $K$ clusters : en effet, il suffit de chercher, pour chacun des éléments de notre dataset, le point de $S$ dont il est le plus proche, on associe dont un point de $S$ (et un seul !) à chacun des éléments de notre dataset. (Remarquez cependant qu'il est possible que certains de ces clusters soient vides.)\n",
    "2. Un ensemble de points de notre dataset peut être représenté par un unique point : le barycentre (ie. la moyenne) de ses points.\n",
    "\n",
    "L'idée de KMeans est alors la suivante :\n",
    "* on commence par choisir un nombre de clusters $K$ ;\n",
    "* ensuite, on tire un ensemble $S$ de $K$ points de notre jeu de données : ces points définissent $K$ clusters (cf. point 1 ci-dessus) ;\n",
    "* puis on itère :\n",
    "    * on attribue à chaque élément de notre dataset le point de $S$ qui en est le plus proche : cela forme $K$  nouveaux clusters ;\n",
    "    * on met à jour nos $K$ points, en prenant pour chaque point le centre du cluster lui correspondant (cf. point 2 ci-dessus).\n",
    "    \n",
    "C'est en fait un algorithme itératif qui cherche le minimum du problème suivant :\n",
    "\n",
    "$$\\mathop{\\mathrm{argmin}}_{s_1,\\dots,s_K}\\sum_{x\\in X}\\bigg(\\min_{k\\in[1,K]}\\Vert x-s_k \\Vert^2\\bigg).$$\n",
    "\n",
    "Ainsi, après assez d'itérations (et on verra comment le choisir), les points ne bougent plus : on a trouvé nos clusters.\n",
    "Néanmoins, le problème d'optimisation décrit ci-dessus est un problème difficile, et il est possible qu'il existe plusieurs solutions à ce problème.\n",
    "Les clusters obtenus à la fin pourront donc varier d'une exécution à l'autre de l'algorithme.\n",
    "Notamment, selon les points $S$ tirés au début, les clusters obtenus pourront être différents."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cette méthode est implémentée dans `sklearn`, testons là sur notre dataset `X_blobs` : on lance la fonction et on affiche 1/ les clusters obtenus et 2/ leurs centres (ie. les points de $S$, en rouge)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.cluster import KMeans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "kmeans = KMeans(n_clusters=3)\n",
    "pred = kmeans.fit_predict(X_blobs)\n",
    "\n",
    "centers = kmeans.cluster_centers_\n",
    "\n",
    "plt.scatter(X_blobs[:,0], X_blobs[:, 1], c=pred, cmap='Dark2')\n",
    "plt.scatter(centers[:,0], centers[:,1], c=\"red\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question 3.** Relancez plusieurs fois la cellule d'au-dessus. Les clusters obtenus sont-ils à chaque fois les mêmes ? Sont-ils toujours dans le même ordre ? Expliquez."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Réponse :*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question 4.** Comme vous le voyez dans la cellule de code précédente, l'argument `n_clusters` indique à `KMeans` combien de clusters rechercher. Lancez l'algorithme en cherchant cette fois-ci $5$ clusters. Commentez le résultat obtenu."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#~~~ lancez l'algorithme pour 5 clusters, commenter ~~~"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Réponse :* "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## K-means à la main\n",
    "\n",
    "Dans cette partie, on va étudier une implémentation de l'algorithme KMeans.\n",
    "Pour cela, on va utiliser les trois fonctions suivantes :\n",
    "* `tirer_points_au_hasard` tire `K` points au hasard dans le dataset `X` ;\n",
    "* `point_plus_proche` renvoie une liste qui contient l'indice du point de `S` le plus proche de chacun des éléments de `X` ;\n",
    "* `barycentre` qui calcule le barycentre des `K` clusters de `X`, l'appartenance de chacun des éléments de `X` étant définie par l'argument `pproche`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def tirer_points_au_hasard(X, K):\n",
    "    id_points = np.random.choice(range(X.shape[0]), K)\n",
    "    return X[id_points].copy()\n",
    "\n",
    "def point_plus_proche(X, S):\n",
    "    dist = ((X[:, np.newaxis,:] - S[np.newaxis,:,:])**2).sum(axis=-1)\n",
    "    return dist.argmin(axis=1)\n",
    "\n",
    "def barycentre(X, K, pproche):\n",
    "    return np.array([np.average(X[pproche==i],axis=0) for i in range(K)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question 5.** En utilisant les trois fonctions ci-dessus, implémentez l'algorithme KMeans, qui prend en argument un dataset `X`, le nombre de clusters `K` et une tolérance `tol`, qui servira de critère d'arrêt, et qui procède ainsi :\n",
    "* tirer `K` points de `X` au hasard dans une variable `S` ;\n",
    "* puis en boucle :\n",
    "    * garder en mémoire les valeurs de `S` ;\n",
    "    * mettre à jour les points de `S` ;\n",
    "    * si la distance entre les nouvelles valeur de `S` et les anciennes est plus petite que `tol`, sortir de la boucle ;\n",
    "* renvoyer `S` une liste qui associe à chaque ligne de `X` le numéro du cluster lui correspondant.\n",
    "    \n",
    "*Indice :* pour calculer la distance entre les anciens points de `S` et les nouveaux points, on gardera en mémoire les valeurs de `S` dans une variable `ancien_S` et on utilisera `np.linalg.norm(S - ancien_S)`. Attention à bien recopier `S` quand vous prenez sa valeur dans `ancien_S`, sinon la valeur sera écrasée !"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def my_kmeans(X, K, tol=0.001):\n",
    "    # ~~~ implémentez la fonction KMeans ~~~\n",
    "    # elle doit renvoyer les points de S et les numéros des clusters pour chacun des points\n",
    "    # sous la forme d'une liste"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question 6.** Lancez votre algorithme sur le dataset `X_blobs` et vérifiez que vous obtenez la même chose qu'au dessus."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ~~~ lancez l'algorithme sur X_blobs ~~~"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ~~~ affichez les résultats ~~~"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Les Limites de KMeans"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question 7.** Reprenez le dataset `X_moons` de la question 2 et lancez l'algorithme KMeans dessus avec $K=2$ clusters. Que dire du résultat ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ~~~ lancez l'algorithme sur X_moons et affichez le résultat ~~~"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Réponse* : "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question 8.** Lancez KMeans avec un nombre de clusters $K$ différent de $2$. Pensez-vous qu'il existe un nombre $K$ qui permet d'obtenir une bonne solution de cette façon ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ~~~ lancez KMeans sur X_moons pour différentes valeurs de K, par exemple 4, 10 et 25, et affichez le résultat ~~~"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Réponse :* peu importe le nombre $K$, la solution ne donne jamais une répartition très satisfaisante."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Spectral Clustering\n",
    "\n",
    "En fait, on peut utiliser des choses que l'on a déjà vues sur les graphes pour améliorer le clustering.\n",
    "En particulier, on avait vu que rechercher les valeurs propres de la matrice Laplacienne d'un graphe permettait de trouver une façon de le dessiner d'une façon assez lisible.\n",
    "\n",
    "On peut donc améliorer l'algorithme de KMeans ci-dessus en l'appliquant non pas directement à nos points, mais à la représentation d'un certain graphe.\n",
    "Il nous reste donc à définir ce graphe...\n",
    "\n",
    "Une idée plutôt féconde est de considérer chacun des points de notre dataset comme un sommet dans un graphe, puis de relier chacun des sommets du graphe aux $K$ sommets les plus proches.\n",
    "Intuitivement, ce graphe devrait être dense (ie. il y aura beaucoup d'arêtes entre les points) au sein de chacun des clusters, et il devrait y avoir relativement peu d'arêtes reliant les points appartenant à différent clusters.\n",
    "\n",
    "Pour notre dataset `X_moons`, on obtiendrait par exemple le graphe suivant :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.neighbors import kneighbors_graph\n",
    "from matplotlib.collections import LineCollection\n",
    "\n",
    "nb_voisins = 50\n",
    "mat = kneighbors_graph(X_moons, nb_voisins, include_self=True)\n",
    "mat_sym = 0.5 * (mat + mat.T)\n",
    "\n",
    "segs = []\n",
    "for i, x in enumerate(X_moons):\n",
    "    for j, y in enumerate(X_moons):\n",
    "        if mat_sym[i,j] > 0:\n",
    "            segs.append((x, y))\n",
    "\n",
    "line_segments = LineCollection(segs, linewidths=0.5, linestyle='solid', color=\"pink\", zorder = -1)\n",
    "\n",
    "fig, ax = plt.subplots(figsize=(10,10))\n",
    "ax.add_collection(line_segments)\n",
    "ax.scatter(X_moons[:, 0], X_moons[:, 1], c=y_moons, cmap=\"Dark2\", alpha=1, s=50)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question 8.** Commentez la répartition des arêtes de ce graphe."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Réponse :*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut maintenant utiliser ce que l'on a vu au TP6 sur la matrice Laplacienne.\n",
    "Pour cela, on utilise la fonction `spectral_embedding` de `sklearn`, qui fait essentiellement ce qu'on a vu dans le TP, mais nous évite de tout réécrire.\n",
    "\n",
    "Cela nous permet de transformer notre dataset ainsi :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.manifold import spectral_embedding\n",
    "\n",
    "X_moons_spec = spectral_embedding(mat_sym, n_components=2, drop_first=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question 9.** Tracer les points dans ce nouvel espace avec leur étiquette réelle. Que constatez-vous ? "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ~~~ tracez le nouveau dataset obtenu et commentez ~~~"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Réponse* :"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question 10.** Relancez KMeans dans ce nouvel espace, toujours avec deux clusters, et affichez les clusters obtenus. Que pensez-vous du résultat ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ~~~ relancez KMeans sur le nouveau dataset ~~~"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ~~~ affichez les résultats sur le dataset original ~~~"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le spectral clustering est très proche de la réalisation d'un spectral embedding suivi d'un K-means.\n",
    "Il est implémenté dans `sklearn`, dans la classe `SpectralClustering`.\n",
    "\n",
    "**Question 11.** Regardez la documentation de `sklearn` pour appliquer `SpectralClustering` sur le jeu de données `X_moons`. Retrouvez-vous bien le résultat obtenu à la question précédente ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ~~~ comparez avec `SpectralClustering` ~~~"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}